The present invention relates generally to digital data communications, and specifically to trellis-based methods for decoding digital signals.
Trellis-based coding and decoding are well known in the art of signal processing. For example, in trellis-coded modulation (TCM), convolutional encoding and constellation mapping is applied to a sequence of input bits, to create encoded symbols to be transmitted over a noisy channel. The encoding introduces xe2x80x9cmemoryxe2x80x9d into the encoded symbols, so that each one depends on the preceding symbols. Practically speaking, trellis-based decoding can be applied to substantially any system that can be represented by a trellis diagram. A trellis-based decoder at the receiving end decodes the received symbols by hypothesizing different possible sequences of input symbols and finding the one that gives a maximum likelihood of being the correct one. Trellis-based decoding can be used in conjunction with a wide range of different coding schemes, as well as for resolving intersymbol interference in communication channels and in other signal processing applications.
In trellis-based decoding, at each point in time, the trellis has a number of vertices corresponding to the number of possible states of the encoding state machine at the corresponding time instant. Transitions between the vertices from one point in time to the next, are henceforth referred to as branches of the trellis, and are associated with the respective symbols that could have caused the transitions. A metric is computed for each branch, indicating the likelihood that the signal actually received at the given point in time resulted from the transmission of the symbol associated with the branch. Typically, the metric of a given branch provides a measure of distance between the received signal and the transmitted branch symbol. In particular, in a Gaussian channel, the logarithm of the likelihood that the received signal corresponds to the transmitted branch symbol reduces to the Euclidean distance between signals. An important property of the distance metric is that the smaller the distance, the greater the likelihood of belonging to the trellis path of the transmitted symbols in the sequence. A path through the trellis is composed of a series of interconnected branches. Each such path thus corresponds to a possible sequence of transmitted symbols and has a path metric equal to the sum of the metrics of its branches. The path with the best metric corresponds to the sequence of symbols with maximum likelihood.
The Viterbi algorithm is a mathematically-optimal maximum likelihood solution to the trellis-based decoding problem. It is described, for example, by Forney in xe2x80x9cThe Viterbi Algorithm,xe2x80x9d published in Proceedings of the IEEE 61(3), pages 268-278 (1973), which is incorporated herein by reference. To streamline the decoding procedure, the Viterbi algorithm retains for each vertex only the one path with the best metric, terminating at the vertex. Other branches, and their corresponding paths, are discarded. The remaining paths at any point in time are referred to as xe2x80x9csurvivors.xe2x80x9d Thus, at each section of the trellis, it is necessary to maintain only as many surviving paths as there are possible states. Nevertheless, when a system has a large number of possible states (as occurs for example in high-performance TCM schemes), the computational burden of tracking all of the survivors is still substantial.
At each step of the decoding procedure, another symbol in the sequence is decoded, by tracing back the most likely path over a certain number of symbols, known as the xe2x80x9cdecision delay.xe2x80x9d Increasing the decision delay generally increases the likelihood of correctly decoding the sequence, but at the same time incurs a greater delay in outputting the decoded symbols.
Conventional implementations of the Viterbi algorithm use two data structures: one to hold the state metrics, and the other for path history (traceback). The data structure of the state metrics holds two sets of old and new state metrics. Each set contains a plurality of state metrics according to the number of states of the encoding system, organized so that the place of the state metric in the structure corresponds to the index of the related state. The traceback data structure is arranged as a table whose dimensions are the number of states of the encoding system and the chosen decision delay. As in the state metrics data structure, the traceback data are stored so that their location in the table corresponds to the index of the related state. Each entry in the table contains a pointer indicating which preceding state was on the surviving path that led to this state.
Each step of a Viterbi decoder corresponds to an input sample to the decoder. In each step, the decoder calculates branch metrics, based on the input sample. Then, based on the old state metrics stored in the data structure and on the calculated branch metrics, a set of new state metrics is calculated. The new state metrics are calculated for each and every state in the trellis. Each new state metric is calculated by an Add/Compare/Select operation, which retains for each state only one path. The Add/Compare/Select operation for a given new state is composed of calculating the metrics for all the paths that terminate in this state, by adding the corresponding old state metrics to the connecting branch metrics, comparing the different path metrics that terminate in this state and selecting only the one path with the best metric.
As noted above, the trellis is processed by tracing back from the current symbol to the decision delay, in order to decode the symbol or bits that were received at a delay corresponding to the decision delay. The traceback starts from the state that has the highest likelihood among all states at the current symbol. The trellis path terminating at this state is declared as the winner path, and the traceback table is used to track the winner path, ending at the state to be decided upon. This path is tracked by reading the entry of the most likely state at the current symbol from the traceback table, and finding the state at the previous symbol that is connected to it on the winner path. This operation steps back one branch on the winner path. From the state found at the previous symbol, the operation is repeated, reading from the traceback table iteratively, until it reaches the earliest symbol in the table. The path thus tracked through the traceback table is the most likely path up to the current symbol. The decoder then returns the symbol or bits corresponding to the earliest transition in the most likely path that was tracked.
Alternative sub-optimal decoding approaches have been proposed, such as the M- and T-algorithms, in order to reduce the number of paths retained. Methods of this type are described, for example, by Simmons, in xe2x80x9cBreadth-First Trellis Decoding with Adaptive Effort,xe2x80x9d published in IEEE Transactions on Communications 38(1), pages 3-12 (1990), by Anderson et al., in xe2x80x9cSequential Coding Algorithms: A Survey and Cost Analysis,xe2x80x9d published in IEEE Transactions on Communications 32(2), pages 169-176 (1984), and by Chennakeshu et al., in U.S. Pat. No. 5,905,742. These publications are incorporated herein by reference. In these methods, the number of survivors at each section of the trellis is restricted to a certain number of paths whose metrics are smaller than a given limit. In the T-algorithm, all paths whose metrics are above a given threshold (T) are discarded. In the M-algorithm, a certain number of states (M) are retained. Simmons and Chennakeshu both describe methods for adaptively varying M or T. As a result, the computational effort required at each decoding stage will tend to vary, leading also to a variable delay between symbols output by the decoder. This effect is very meaningful in T-algorithm, where the number of surviving paths can change significantly from one symbol to another, even for a fixed threshold. Simmons considers but rejects the idea of purging all but the path of the best metric in any group of paths that lead to a common state, as in the Viterbi algorithm. He notes that this additional step of path purging would require extra work and additional hardware (for VLSI implementation), while yielding only a marginal reduction in the average number of survivors to be processed.
It is an object of the present invention to provide improved methods and devices for trellis-based decoding.
It is a further object of some aspects of the present invention to provide methods for trellis-based decoding that are suited to VLSI implementation with reduced computational load.
In preferred embodiments of the present invention, a digital data receiver decodes a stream of symbols by combining Viterbi-type state-based trellis decoding with threshold-based path selection. At each step in decoding the trellis of possible states, the number of paths is pruned so that only one path reaches each new state, as in Viterbi decoding. Then some of the new states are pruned so that only states having a corresponding path metric below a chosen threshold are preserved for use in extending the possible paths at the next step.
This combination of path pruning and state pruning provides enhanced computational efficiency, particularly in applications in which the encoding system may have a large number of states. A novel parallel processing architecture and data structure are preferably used to overcome the difficulties of combining path purging and state purging that have prevented this technique from being practically implemented in the past. While preferred embodiments are described herein with reference to decoding trellis-coded signals by minimizing appropriate distance metrics, the principles of the present invention may be applied, mutatis mutandis, to estimation of state sequences of other finite-state processes by maximizing or minimizing appropriate metrics.
There is therefore provided, in accordance with a preferred embodiment of the present invention, a method for decoding a sequence of symbols encoded by an encoding system with a plurality of possible states and transmitted over a channel, wherein the encoding system output can be represented by a trellis diagram, the method including:
receiving a signal corresponding to the sequence of symbols transmitted over the channel;
responsive to the signal, finding respective old state metrics for one or more of the possible states of the encoding system that correspond to a given symbol in the sequence;
determining respective transition metrics for state transitions that link the one or more possible states for which the old state metrics were found to at least some of the possible states of the encoding system that correspond to a succeeding one of the symbols in the sequence;
computing new state metrics for the at least some of the possible states that correspond to the succeeding symbol, responsive to the respective old state metrics and to the transition metrics, such that when two or more of the transitions are linked to the same one of the possible states of the succeeding symbol, one of the transitions is chosen based on a criterion applied to the new state metrics;
selecting a subset of the at least some of the possible states that correspond to the succeeding symbol based on the new state metrics; and
decoding the sequence of symbols based on the selected subset.
Preferably, each of the state metrics is indicative of a likelihood that the corresponding state lies on a trellis path of the transmitted symbols in the sequence. Most preferably, computing the new state metrics includes, when two or more of the transitions are linked to the same one of the possible states that correspond to the succeeding symbol, choosing the one of the transitions having the highest likelihood of belonging to the Trellis path of the transmitted symbols in the sequence. Alternatively or additionally, selecting the subset of the at least some of the possible states includes selecting the states having substantially the greatest likelihood of belonging to the trellis path of the transmitted symbols in the sequence, as indicated by the corresponding new state metrics.
Preferably, the trellis diagram includes a trellis of vertices linked by branches, in which the vertices correspond respectively to the possible states of the encoding system, and the branches correspond respectively to the possible transitions between the encoding system states, and finding the old state metrics includes:
selecting respective paths through the trellis leading up to the one or more of the possible states that correspond to the given symbol, each path including a linked series of the branches through the trellis, by purging the states that corresponds to the given symbol so that the one or more of the possible states include only those states whose old state metrics indicate that they have the greatest likelihood of belonging to the trellis path of the transmitted symbols in the sequence;
calculating respective path metrics for the selected paths; and
setting the old state metrics equal to the respective path metrics.
In a preferred embodiment, the sequence of symbols is encoded and modulated using trellis-coded modulation.
Preferably, determining the transition metrics includes finding a measure of a distance, such that the smaller the distance, the greater the likelihood of belonging to a trellis path of the transmitted symbols in the sequence, and selecting the subset includes setting a threshold, and selecting the subset of the possible states having corresponding new state metrics smaller than the threshold.
Alternatively or additionally, determining the transition metrics includes finding a measure of a distance, such that the smaller the distance, the greater the likelihood of belonging to a trellis path of the transmitted symbols in the sequence, and computing the new state metrics includes selecting, among the two or more of the transitions that are linked to the same one of the possible states that corresponds to the succeeding symbol, the transition corresponding to the path with the lowest metric.
Further additionally or alternatively, finding the respective old state metrics includes storing the old state metrics in a data structure with an index indicating the states that correspond to the succeeding symbol, and with a pair of state metrics of a corresponding pair of states that correspond to the given symbol, from which the states that corresponds to the succeeding symbol are reached by the transitions.
Preferably, the method includes repeating, with respect to a further one of the symbols in the sequence subsequent to the succeeding one of the symbols, the steps of determining the transition metrics, computing the new state metrics, and selecting the subset of the possible states, using the at least some of the possible states of the succeeding symbol that are in the selected subset in place of the one or more of the possible states that correspond to the given symbol, and using the corresponding new state metrics in place of the respective old state metrics, so as to find a further subset of the states of the further one of the symbols for use in decoding the sequence of symbols.
There is also provided, in accordance with a preferred embodiment of the present invention, a method for trellis-based decoding, including:
receiving a signal corresponding to a sequence of symbols transmitted over a channel;
responsive to the signal, finding respective old state metrics for one or more of the possible states of the encoding system that correspond to a given symbol in the sequence;
determining respective transition metrics for state transitions that link the one or more possible states for which the old state metrics were found to at least some of the possible states of the encoding system that correspond to a succeeding one of the symbols in the sequence;
computing new state metrics for the at least some of the possible states that correspond to the succeeding symbol, responsive to the respective old state metrics and to the transition metrics; and
decoding the sequence of symbols based on the selected subset,
wherein finding the respective old state metrics includes storing the old state metrics in a data structure with a pair of state metrics of a corresponding pair of the possible states that corresponds to the given symbol, from which pair the possible states that correspond to the succeeding symbol are reached by the transitions.
Preferably, computing the new state metrics includes storing a list indicating a selected group of the one or more of the possible states that correspond to the given symbol with respect to which the new state metrics are to be calculated, and reading the data from the data structure responsive to the list. Alternatively, computing the new state metrics includes storing a list indicating a selected group of the one or more of the possible states that correspond to the succeeding symbol for which the new state metrics are to be calculated, and reading the data from the data structure responsive to the list.
Preferably, the data structure is packed so as to delete the possible states that correspond to the given symbol that are not in a selected group of the one or more of the possible states that correspond to the given symbol with respect to which the new state metrics are to be calculated. Most preferably, the indices in the data structure create a list indicating a selected group of the one or more of the possible states that correspond to the given symbol with respect to which the new state metrics are to be calculated, and computing the new state metrics includes reading data from the data structure responsive to the list. Alternatively or additionally, the indices in the data structure create a list indicating a selected group of the one or more of the possible states that correspond to the succeeding symbol for which the new state metrics are to be calculated, and computing the new state metrics includes reading the data from the data structure responsive to the list.
Alternatively, the data structure is unpacked so as to comprise an entry for each and every pair of the possible states of the encoding system that correspond to the given symbol.
Preferably, each value of the index of the data structure corresponds to a pair of the possible states that correspond to the succeeding symbol. Most preferably, each of the possible states that correspond to the succeeding symbol is identified by a number, and wherein a most significant bit of the number is omitted in order to generate the value of the index for the pair of the possible states.
Further preferably, computing the new state metrics includes computing the metrics for both of the pair of the possible states that correspond to the succeeding symbol substantially simultaneously. Most preferably, selecting the subset of the at least some of the possible states that correspond to the succeeding symbol includes determining substantially simultaneously, for each of the pair of the possible states, whether to include the state in a subset selected from the at least some of the possible states that correspond to the succeeding symbol based on the new state metrics for use in decoding the sequence of symbols.
There is additionally provided, in accordance with a preferred embodiment of the present invention, decoder apparatus, adapted to receive a sequence of samples of a signal, corresponding to a sequence of symbols encoded by an encoding system with a plurality of possible states, and including:
a memory, adapted to store respective old state metrics, determined responsive to the samples, for one or more of the possible states that correspond to a given symbol in the sequence of symbols, each such state metric indicative of a likelihood that the corresponding state lies on a trellis path for the transmitted symbols in the sequence;
a branch metric processor, coupled to receive the sequence of samples, and adapted to determine, responsive to the samples, respective transition metrics for state transitions that link the one or more possible states that correspond to the given symbol to at least some of the possible states that correspond to a succeeding one of the symbols in the sequence;
at least one add-compare-select processor, coupled to receive the transition metrics and further coupled to read the old state metrics from the memory, and to compute new state metrics for the at least some of the possible states that correspond to the succeeding symbol based on the respective old state metrics and the transition metrics, such that when two or more of the transitions are linked to the same one of the possible states that corresponds to the succeeding symbol, the transition having the highest likelihood of belonging to the trellis path is chosen, and further adapted to select a subset of the at least some of the possible states that correspond to the succeeding symbol having the greatest likelihood, as indicated by the corresponding new state metrics, of belonging to the trellis path; and
a decision device, adapted to decode the sequence of symbols based on the selected subset.
There is further provided, in accordance with a preferred embodiment of the present invention, trellis decoding apparatus, including:
an input buffer adapted to receive a sequence of samples of a signal, corresponding to a sequence of symbols encoded by an encoding system with a plurality of possible states;
a trellis decoder, adapted to decode the sequence by processing a variable number of trellis states that correspond to different symbols in the sequence, thereby generating output data at a variable decoding rate; and
an output buffer, coupled to receive and buffer the output data so that the data could be read out of the apparatus at a substantially constant output rate.
There is moreover provided, in accordance with a preferred embodiment of the present invention, decoder apparatus, adapted to receive a sequence of samples of a signal, corresponding to a sequence of symbols encoded by an encoding system with a plurality of possible states and transmitted over a channel, wherein the encoding system output can be represented by a trellis diagram, the decoder including:
a memory, adapted to store respective old state metrics for one or more of the possible states of the encoding system that correspond to a given symbol in the sequence;
a branch metric processor, coupled to receive the sequence of samples, and adapted to determine, responsive to the samples, respective transition metrics for state transitions that link the one or more possible states for which the old state metrics were found to at least some of the possible states of the encoding system that correspond to a succeeding one of the symbols in the sequence;
at least one add-compare-select processor, coupled to receive the transition metrics and further coupled to read the old state metrics from the memory, and to compute new state metrics for the at least some of the possible states that correspond to the succeeding symbol, responsive to the respective old state metrics and to the transition metrics; and
a decision device, adapted to decode the sequence of symbols based on the new state metrics,
wherein the memory is configured to store the old state metrics in a data structure including one or more entries, wherein each of the entries includes a pair of state metrics of a corresponding first pair of the possible states that corresponds to the given symbol, from which a second pair of the possible states that correspond to the succeeding symbol are reached by the transitions.
Preferably, when a quantity of the output data in the output buffer drops below a predetermined level, the decoder is prompted to increase the rate of generating the output data. Additionally or alternatively, the decoder decodes the sequence by evaluating the trellis states over a selected decision delay, and responsive to the prompt to increase the rate of generating the output data, the decoder alters the decision delay.
There is moreover provided, in accordance with a preferred embodiment of the present invention, a method for trellis decoding, including:
receiving a sequence of samples of a signal, corresponding to a sequence of symbols encoded by an encoding system with a plurality of possible states;
decoding the sequence using a trellis decoder with a variable computational effort, thereby generating output data at a variable decoding rate; and
storing the output data in an output buffer, from which the data can be read out at a substantially constant output rate.
In a preferred embodiment, decoding the sequence includes processing a variable number of trellis states that correspond to different symbols in the sequence.
The present invention will be more fully understood from the following detailed description of the preferred embodiments thereof, taken together with the drawings in which: